home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / c / ldb.zip / BINDER.CPP < prev    next >
C/C++ Source or Header  |  1991-10-18  |  13KB  |  685 lines
  1. /*
  2.  
  3.     binder.cpp
  4.     10-18-91
  5.     Loose Data Binder v 1.4
  6.  
  7.     Copyright 1991
  8.     John W. Small
  9.     All rights reserved
  10.  
  11.     PSW / Power SoftWare
  12.     P.O. Box 10072
  13.     McLean, Virginia 22102 8072 USA
  14.  
  15.     John Small
  16.     Voice: (703) 759-3838
  17.     CIS: 73757,2233
  18.  
  19. */
  20.  
  21.  
  22. #include <string.h>
  23. #include "binder.hpp"
  24.  
  25. void Binder::construct(unsigned flags, unsigned maxNodes,
  26.     unsigned limit, unsigned delta)
  27. {
  28.     curNode = first = nodes = 0;
  29.     comparE = BDRcomparE0;
  30.  
  31. /*
  32.     The following relationships are maintained
  33.     during operation of a binder:
  34.  
  35.     1 <= delta <= lowLimit <= limit <= maxNodes
  36.         <= BDR_MAXNODES
  37.     lowThreshold = lowLimit - delta;
  38. */
  39.  
  40.     if (maxNodes > BDR_MAXNODES)
  41.         maxNodes = BDR_MAXNODES;
  42.     if (limit > maxNodes)
  43.         limit = maxNodes;
  44.     if (delta > limit)
  45.         delta = limit;
  46.     if (!delta)  {
  47.         delta = 1;
  48.         if (limit < delta)
  49.             limit = delta;
  50.         if (maxNodes < limit)
  51.             maxNodes = limit;
  52.     }
  53.     if ((linkS = new voiD[limit]) == voiDV0)
  54.         this->limit = lowLimit = lowThreshold
  55.             = this->delta = this->maxNodes
  56.             = this->flags = 0;
  57.     else  {
  58.         this->limit = limit;
  59.         this->delta = delta;
  60.         this->maxNodes = maxNodes;
  61.         lowLimit = limit;
  62.         lowThreshold = lowLimit - delta;
  63.         this->flags = ((flags & BDR_OK_FREE) 
  64.             | BDR_SORTED);
  65.     }
  66. }
  67.  
  68. Binder::Binder(voiDV argv, int argc, unsigned flags)
  69. {
  70.     construct(flags,BDR_MAXNODES,argc,BDR_DELTA);
  71.     if (argv) if (argc > 0)
  72.         while (argc--)
  73.             push(argv[argc]);
  74.     else
  75.         for (argc = 0; insQ(argv[argc]); argc++);
  76. }
  77.  
  78. voiDV Binder::vector()
  79. {
  80.     voiDV V = voiDV0;
  81.  
  82.     if (nodes) if ((V = new voiD[nodes+1]) != voiDV0)  {
  83.         for (unsigned i = 0; i < nodes; i++)
  84.             V[i] = atGet(i);
  85.         V[i] = voiD0;
  86.     }
  87.     return V;
  88. }
  89.  
  90. Binder::~Binder()
  91. {
  92.     if (flags & BDR_OK_FREE)
  93.         allFree();
  94.     else
  95.         allDel();
  96.     if (linkS)
  97.         delete linkS;
  98. }
  99.  
  100. unsigned Binder::setLimit(unsigned newLimit)
  101. {
  102.     voiDV newLinkS;
  103.     unsigned i;
  104.  
  105.     if (newLimit < nodes)
  106.         newLimit = nodes;
  107.     else if (newLimit > maxNodes)
  108.         newLimit = maxNodes;
  109.     if (newLimit < delta)
  110.         newLimit = delta;
  111.     if (!linkS || !newLimit || newLimit == limit)
  112.         return 0;
  113.     if ((newLinkS = new voiD[newLimit]) == voiDV0)
  114.         return 0;
  115.     if ((i = limit - first) > nodes)
  116.         i = nodes;
  117.     memcpy(newLinkS,&linkS[first],sizeof(linkS[0])*i);
  118.     /* copy wrap around */
  119.     if (i < nodes)
  120.         memcpy(&newLinkS[i],linkS,
  121.             sizeof(linkS[0])*(nodes-i));
  122.     if (newLimit > limit)
  123.         if (newLimit - delta > limit)
  124.             lowLimit = newLimit - delta;
  125.         else
  126.             lowLimit = limit;
  127.     else
  128.         if (newLimit - delta > delta)
  129.             lowLimit = newLimit - delta;
  130.         else
  131.             lowLimit = delta;
  132.     lowThreshold = lowLimit - delta;
  133.     delete linkS;
  134.     linkS = newLinkS;
  135.     limit = newLimit;
  136.     first = 0;
  137.     return limit;
  138. }
  139.  
  140. unsigned Binder::setDelta(unsigned newDelta)
  141. {
  142.     return ((newDelta && newDelta <= lowLimit)?
  143.         delta = newDelta : 0);
  144. }
  145.  
  146. unsigned Binder::setMaxNodes(unsigned newMaxNodes)
  147. {
  148.     return ((newMaxNodes >= limit)?
  149.         (maxNodes = (newMaxNodes
  150.         > BDR_MAXNODES)? BDR_MAXNODES
  151.         : newMaxNodes) : 0);
  152. }
  153.  
  154. voiD Binder::atIns(unsigned n, const voiD D)
  155. {
  156.     voiDV newLinkS;
  157.     unsigned newLimit, i;
  158.  
  159.     if (!linkS || !D)
  160.         return voiD0;
  161.     if (nodes == limit)  {
  162.         if (limit == maxNodes)
  163.             return voiD0;
  164.         newLimit = (maxNodes - delta > limit)?
  165.             limit + delta : maxNodes;
  166.         if ((newLinkS = new voiD[newLimit])
  167.             == voiDV0) return voiD0;
  168.         if ((i = limit - first) > nodes)
  169.             i = nodes;
  170.         memcpy(newLinkS,&linkS[first],
  171.             sizeof(linkS[0])*i);
  172.         /* copy wrap around */
  173.         if (i < nodes)
  174.             memcpy(&newLinkS[i],linkS,
  175.                 sizeof(linkS[0])*(nodes-i));
  176.         /*
  177.             Compute next smaller linkS size
  178.             and threshold for shrinking.
  179.         */
  180.         lowLimit = limit;
  181.         lowThreshold = lowLimit - delta;
  182.         /* swap new for old */
  183.         delete linkS;
  184.         linkS = newLinkS;
  185.         limit = newLimit;
  186.         first = 0;
  187.     }
  188.     if (!Dattach(D))
  189.         return voiD0;
  190.     if (!n)  /* push */
  191.         linkS[first? --first
  192.             : (first = limit - 1)] = D;
  193.     else if (n >= nodes) /* insQ */
  194.         linkS[(first+(n=nodes))%limit] = D;
  195.     else  { /* insert interior */
  196.         i = (first + n) % limit;
  197.         if (i < first || !first)
  198.             /* move rear rightward */
  199.             memmove(&linkS[i+1],&linkS[i],
  200.                 sizeof(linkS[0])
  201.                 * (nodes-n));
  202.         else /* move front leftward */
  203.             memmove(&linkS[--first],&linkS[--i],
  204.                 sizeof(linkS[0])*(n+1));
  205.         linkS[i] = D;
  206.     }
  207.     nodes++;
  208.     if (n <= curNode)
  209.         curNode++;
  210.     flags &= ~BDR_SORTED;
  211.     return D;
  212. }
  213.  
  214. voiD Binder::atDel(unsigned n)
  215. {
  216.     voiDV newLinkS;
  217.     unsigned newLimit, i;
  218.     voiD D;
  219.  
  220.     if (!linkS || n >= nodes)
  221.         return voiD0;
  222.     D = linkS[(first+n)%limit];
  223.     if (!n)  {  /* pop */
  224.         if (++first >= limit)
  225.             first = 0;
  226.     }
  227.     else if (n != nodes-1)  {  /* del interior */
  228.         /* move front rightward */
  229.         memmove(&linkS[first+1],&linkS[first],
  230.             sizeof(linkS[0])*n);
  231.         first++;
  232.     }
  233.     if (--nodes == 0)
  234.         flags |= BDR_SORTED;
  235.     if (n < curNode)
  236.         curNode--;
  237.     else if (n == curNode)
  238.         curNode = nodes;
  239.     if (nodes < lowThreshold)  {
  240.         newLimit = lowLimit;
  241.         if ((newLinkS = new voiD[newLimit])
  242.             != voiDV0)  {
  243.             if ((i = limit - first) > nodes)
  244.                 i = nodes;
  245.             memcpy(newLinkS,&linkS[first],
  246.                 sizeof(linkS[0])*i);
  247.             /* copy wrap around */
  248.             if (i < nodes)
  249.                 memcpy(&newLinkS[i],linkS,
  250.                     sizeof(linkS[0])
  251.                     *(nodes-i));
  252.             /*
  253.                 Compute next smaller linkS
  254.                 size and threshold for 
  255.                 shrinking.
  256.             */
  257.             if (lowLimit - delta > delta)
  258.                 lowLimit -= delta;
  259.             else
  260.                 lowLimit = delta;
  261.             lowThreshold = lowLimit - delta;
  262.             /* swap new for old */
  263.             delete linkS;
  264.             linkS = newLinkS;
  265.             limit = newLimit;
  266.             first = 0;
  267.         }
  268.     }
  269.     Ddetach(D);
  270.     return D;
  271. }
  272.  
  273. int Binder::allDel()
  274. {
  275.     if (!linkS)
  276.         return 0;
  277.     for (unsigned i = 0; i < nodes; /* no reinit */)
  278.         if (!atDel(i))
  279.             i++;
  280.     return (nodes? 0 : 1);
  281. }
  282.  
  283. int Binder::allFree()
  284. {
  285.     if (!linkS)
  286.         return 0;
  287.     if (flags & BDR_OK_FREE)
  288.         for (unsigned i = 0; i < nodes; 
  289.             /* no reinit */)
  290.             if (!Dfree(atDel(i)))
  291.                 i++;
  292.     return (nodes? 0 : 1);
  293. }
  294.  
  295. voiD Binder::atPut(unsigned n, const voiD D)
  296. {
  297.     if (linkS && D && (n < nodes))
  298.         if (Dattach(D))  {
  299.             flags &= ~BDR_SORTED;
  300.             voiD& N = linkS[(first+n)%limit];
  301.             Ddetach(N);
  302.             DFREE(N);
  303.             return (N=D);
  304.         }
  305.     return voiD0;
  306. }
  307.  
  308. voiD Binder::atGet(unsigned n)
  309. {
  310.     return ((linkS && (n < nodes))?
  311.         linkS[(first+n)%limit] : voiD0);
  312. }
  313.  
  314. voiD Binder::atXchg(unsigned n, const voiD D)
  315. {
  316.     if (linkS && D && (n < nodes))
  317.         if (Dattach(D))  {
  318.             flags &= ~BDR_SORTED;
  319.             voiD& N = linkS[(first+n)%limit];
  320.             voiD oldD = N;
  321.             N = D;
  322.             Ddetach(oldD);
  323.             return oldD;
  324.         }
  325.     return voiD0;
  326. }
  327.  
  328. unsigned Binder::index(const voiD D)
  329. {
  330.     unsigned i;
  331.  
  332.     if (linkS && D)
  333.         for (i = 0; i < nodes; i++)
  334.             if (D == linkS[(first+i)%limit])
  335.                 return i;
  336.     return BDR_NOTFOUND;
  337. }
  338.  
  339. int Binder::forEach(BDRforEachBlocK B, voiD M, voiD A)
  340. {
  341.     unsigned i;
  342.  
  343.     if (!linkS || !B || !nodes)
  344.         return 0;
  345.     for (i = 0; i < nodes; i++)
  346.         (*B)(linkS[(first+i)%limit],M,A);
  347.     return 1;
  348. }
  349.  
  350. unsigned Binder::firstThat(BDRdetectBlocK B, voiD M)
  351. {
  352.     unsigned i;
  353.  
  354.     if (linkS && B)
  355.         for (i = 0; i < nodes; i++)
  356.             if ((*B)(linkS[(first+i)%limit],M))
  357.                 return i;
  358.     return BDR_NOTFOUND;
  359. }
  360.  
  361. unsigned Binder::lastThat(BDRdetectBlocK B, voiD M)
  362. {
  363.     unsigned i;
  364.  
  365.     if (linkS && B && nodes)
  366.         for (i = nodes; i--; /* no reinit */)
  367.             if ((*B)(linkS[(first+i)%limit],M))
  368.                 return i;
  369.     return BDR_NOTFOUND;
  370. }
  371.  
  372. int Binder::collect(BDRcollectBlocK B, BindeR R,
  373.     voiD M, voiD A)
  374. {
  375.     unsigned i;
  376.  
  377.     if (!linkS || !B || !R)
  378.         return 0;
  379.     for (i = 0; i < nodes; i++)
  380.         (*B)(linkS[(first+i)%limit],R,M,A);
  381.     return 1;
  382. }
  383.  
  384.  
  385. /*  FlexList like primitives:  */
  386.  
  387. unsigned Binder::CurNode()
  388. {
  389.     return ((curNode < nodes)?
  390.         curNode : BDR_NOTFOUND);
  391. }
  392.  
  393. int  Binder::setCurNode(unsigned n)
  394. {
  395.     return ((curNode = ((n > nodes)? nodes : n))
  396.         < nodes);
  397. }
  398.  
  399. Binder& Binder::operator<<(Binder& (*manipulator)
  400.         (Binder& B))
  401. {
  402.     return (manipulator? (*manipulator)(*this)
  403.         : *this);
  404. }
  405.  
  406. voiD Binder::ins(const voiD D)
  407. {
  408.     if (atIns(curNode+1,D))  {
  409.         if (++curNode >= nodes)
  410.             curNode = nodes - 1;
  411.         return D;
  412.     }
  413.     return voiD0;
  414. }
  415.  
  416. voiD Binder::insSort(